Commonly, network devices operate one or more routing/forwarding protocols, such as the Border Gateway Protocol (BGP), that associate a destination address prefix (“prefix”) with a particular next-hop node (“next-hop”) from the network device. In order to send traffic (e.g., packets) to the prefix, the network device sends the traffic to the associated next-hop, which may continue (e.g., “hop-by-hop”) to the destination. A BGP next-hop, for example, is generally the next BGP node that is to be used to reach the particular prefix (which may require first traversing one or more interior next-hops on the way to the BGP next-hop). In addition, as will be understood by those skilled in the art, virtual private networks (VPNs) may be used to segment the network into a plurality of “private” networks that may be used to differentiate traffic traversing shared/common links. For instance, for a particular network (e.g., a provider network), multiple border nodes may advertise reachability for the same VPN prefix, where each border node associates a different VPN label used to reach the destination VPN prefix.
The network device often stores its routing information in a routing table (e.g., using information in a BGP table and other sources, such as interior gateway protocols, or IGPs) that is a searchable data structure in which prefixes are mapped to their associated routing information (e.g., next-hops) and their associated labels. In particular, for use with VPN prefixes, multiple corresponding virtual routing/forwarding (VRF) instances may be used, as will be understood by those skilled in the art. As the routing information changes, the routing tables (and/or VRF instances) are updated accordingly. Moreover, the routing tables may also be used to create a forwarding table or “Forwarding Information Base” (FIB), which the network device uses to forward the traffic. Changes to the routing tables, therefore, may eventually propagate into the FIB to effectuate a forwarding change.
Often, the time to add, modify, or delete entries in a routing table is a belabored process. For instance, each prefix in a routing table is generally linked to a particular next-hop as a tightly bound pair. When the next-hop is changed for a particular prefix, the prefix must be “re-linked” to the new next hop. On a singular basis, this may not be especially burdensome. However, when a substantially large number of prefixes populate the routing tables (e.g., 400-800K VPN prefixes), and where a single next-hop change (e.g., due to next-hop failure, modification, or other topology change) applies to a large number of those prefixes, the per-prefix re-linking/updating (“convergence”) may require a substantial amount of time, which is often unacceptable. Further, because of the time required to complete the convergence, traffic may be lost until the FIB has been properly updated to reflect the change in the network topology (e.g., sending traffic to a failed next-hop node).